
//1786.从第一个节点出发到最后一个节点的受限路径数
class Solution {
    #define MOD 1000000007
public:
    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        //Dijkstra + DFS
        //使用Dijkstra算法求出从n-1位置开始到每个位置的最短路路径
        //再使用DFS从0位置开始找路径长度依次递减并且能到n-1位置的路径个数

        //使用Dijkstra算法
        vector<vector<pair<int,int>>> path(n);      //记录每个位置之间的路径关系
        for(auto& nums: edges)
        {
            int x = nums[0] - 1 , y = nums[1] - 1 ,t = nums[2];
            path[x].emplace_back(y,t);
            path[y].emplace_back(x,t);
        }
        vector<int> dis(n,INT_MAX);
        vector<int> vist(n);
        priority_queue<pair<int,int> ,vector<pair<int,int>>,greater<pair<int,int>>> pq;
        pq.push({0,n-1});
        vist[n-1] = 0;

        while(pq.size())
        {
            auto [clock,pos] = pq.top();
            pq.pop();
            if(dis[pos] <= clock) continue;
            vist[pos] = 1;
            dis[pos] = clock;

            for(auto& [next,t] : path[pos])
                if(clock + t <dis[next] && !vist[next]) pq.push({clock + t,next});
        }

        //使用DFS找路径
        vector<int> have_go(n);
        vector<int> each_pos(n,-1);                                         //存储已经到的位置的路径长度
        function<int(int,vector<int>&)> dfs = [&](int pos,vector<int>& hg)  //进行DFS,其中hg表示当前路径已经遍历过的位置
        {
            if(pos == n-1) return 1;
            if(each_pos[pos] != -1) return each_pos[pos];
            int ret = 0;
            for(auto& [next,_] : path[pos])
            {
                if(!hg[pos] &&dis[next] < dis[pos]) 
                {
                    hg[pos] = 1;
                    ret = (ret + dfs(next,hg)%MOD)%MOD;
                    hg[pos] = 0;
                }
            }
            each_pos[pos] = ret;
            return ret;
        };

        return dfs(0,have_go);
    }
};